Grokking Meta Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Meta Easy Problems
Toeplitz Matrix (easy)
Solution: Toeplitz Matrix
Remove All Adjacent Duplicates In String (easy)
Solution: Remove All Adjacent Duplicates In String
Minimum Depth of a Binary Tree (easy)
Solution: Minimum Depth of a Binary Tree
Tree Diameter (easy)
Solution: Tree Diameter
Island Perimeter (easy)
Solution: Island Perimeter
Moving Average from Data Stream (easy)
Solution: Moving Average from Data Stream
Move Zeroes (easy)
Solution: Move Zeroes
Missing Ranges (easy)
Solution: Missing Ranges
Palindrome Permutation (easy)
Solution: Palindrome Permutation
Rank Transform of an Array (easy)
Solution: Rank Transform of an Array
Meta Medium Problems
Diagonal Traverse (medium)
Solution: Diagonal Traverse
Shortest Path in Binary Matrix (medium)
Solution: Shortest Path in Binary Matrix
Maximum Swap (medium)
Solution: Maximum Swap
Custom Sort String (medium)
Solution: Custom Sort String
Binary Tree Vertical Order Traversal (medium)
Solution: Binary Tree Vertical Order Traversal
Buildings With an Ocean View (medium)
Solution: Buildings With an Ocean View
Basic Calculator II (medium)
Solution: Basic Calculator II
Nested List Weight Sum (medium)
Solution: Nested List Weight Sum
Dot Product of Two Sparse Vectors (medium)
Solution: Dot Product of Two Sparse Vectors
Max Consecutive Ones III (medium)
Solution: Max Consecutive Ones III
Subarray Sum Equals K (medium)
Solution: Subarray Sum Equals K
Next Permutation (medium)
Solution: Next Permutation
Simplify Path (medium)
Solution: Simplify Path
Lowest Common Ancestor of a Binary Search Tree (medium)
Solution: Lowest Common Ancestor of a Binary Search Tree
'K' Closest Points to the Origin (medium)
Solution: 'K' Closest Points to the Origin
Sum of Path Numbers (medium)
Solution: Sum of Path Numbers
Merge Intervals (medium)
Solution: Merge Intervals
Right View of a Binary Tree (medium)
Solution: Right View of a Binary Tree
Number of Islands (medium)
Solution: Number of Islands
Clone Graph (medium)
Solution: Clone Graph
Missing Element in Sorted Array (medium)
Solution: Missing Element in Sorted Array
Number of Substrings Containing All Three Characters (medium)
Solution: Number of Substrings Containing All Three Characters
Capacity To Ship Packages Within D Days (medium)
Solution: Capacity To Ship Packages Within D Days
Count and Say (medium)
Solution: Count and Say
Contiguous Array (medium)
Solution: Contiguous Array
Sliding Window Median (hard)
Solution: Sliding Window Median
Alien Dictionary (hard)
Solution: Alien Dictionary
Minimum Window Substring (hard)
Solution: Minimum Window Substring
Best Meeting Point (hard)
Solution: Best Meeting Point
Maximum Sum of 3 Non-Overlapping Subarrays (hard)
Solution: Maximum Sum of 3 Non-Overlapping Subarrays
Making A Large Island (hard)
Solution: Making A Large Island
Basic Calculator (Hard)
Solution: Basic Calculator
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Longest Increasing Path in a Matrix (hard)
Solution: Longest Increasing Path in a Matrix
Valid Palindrome III (hard)
Solution: Valid Palindrome III
Solution: Buildings With an Ocean View

Problem Statement

You are given an array heights of size n, representing the heights of n buildings.

The ocean is to the right of these buildings. A building has an ocean view if there are no taller buildings to its right.

The task is to find the indices(0-based) of all such buildings with an ocean view.

Examples

  • Example 1:

    • Input: [4, 3, 2, 1]
    • Expected Output: [0, 1, 2, 3]
    • Justification: Each building is shorter than the one to its left, hence all have an ocean view.
  • Example 2:

    • Input: [2, 3, 1, 4]
    • Expected Output: [3]
    • Justification: Building at index 3 is the only one without taller buildings to their right.
  • Example 3:

    • Input: [7, 4, 3, 2, 1, 4, 6, 3]
    • Expected Output: [0, 6, 7]
    • Justification: Buildings at indices 0, 6, and 7 are the only ones without taller buildings to their right.

Constraints:

  • 1 <= heights.length <= 105
  • 1 <= heights[i] <= 109

Solution

To solve this problem, the most effective approach is to traverse the array of buildings from right to left, maintaining a record of the tallest building encountered so far. This direction of traversal is crucial because it allows us to easily determine whether a building has a taller one to its right. By keeping track of the maximum height encountered, we can identify which buildings have an unobstructed view of the ocean.

The reason why this approach is efficient lies in its simplicity and the reduction of unnecessary comparisons. Instead of comparing each building with all others to its right, we only compare it with the maximum height encountered so far. This significantly reduces the number of comparisons and makes the algorithm efficient for large lists of buildings.

Step-by-step Algorithm

  • Initialize an empty list result to store indices of buildings with ocean views.
  • Initialize a variable maxHeight to 0 to keep track of the tallest building seen so far.
  • Traverse the array from the last element to the first:
    • If the current building's height is greater than maxHeight:
      • Add the current index to result.
      • Update maxHeight to the current building's height.
  • Reverse the result list to maintain the original order of buildings.
  • Return the result list.

Algorithm Walkthrough

Image
  • Step 1: Initialize result = [], maxHeight = 0.
  • Step 2: Start from the last building (height 3). 3 > 0, so add index 7 to result, update maxHeight to 3. result = [7].
  • Step 3: Move to the second-last building (height 6). 6 > 3, so add index 6 to result, update maxHeight to 6. result = [7, 6].
  • Step 4: Move to the index 5. building height = 4. 4 < 6, do nothing.
  • Step 5: Move to the index 4. building height = 1. 1 < 6, do nothing.
  • Step 6: Move to the index 3. building height = 2. 2 < 6, do nothing.
  • Step 7: Move to the index 2. building height = 3. 3 < 6, do nothing.
  • Step 8: Move to the index 1. building height = 4. 4 < 6, do nothing.
  • Step 9: Move to the index 0. building height = 7. 7 > 6, so add index 0 to result and update maxHeight to 7. result = [7, 6, 0].
  • Step 7: Reverse result to [7, 6, 0].
  • Final Output: [0, 6, 7].

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

  • Time Complexity: The time complexity of the algorithm is O(N), where N is the number of buildings. This is because we traverse the list of buildings once from right to left.

  • Space Complexity: The space complexity is O(N) in the worst case, where all buildings have an ocean view. This space is used to store the indices of buildings in the result list. In practical scenarios, the space used would be less than O(N) as not all buildings will have an ocean view.

Buildings With an Ocean View (medium)
Basic Calculator II (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis